from pile import PileDyna
def suite_croissante(tab):
"""
Fonction qui cherche laplus grande suite croissante dans un tableau de valeurs
Entrée: un tableau de valeurs (list[int])
Sortie: la plus longue suite croissante sous forme de tableau (list[int]) et la longueur de cette suite(int)
"""
pile_actuelle=PileDyna() # Pile de la suite actuelle
meilleure_pile=PileDyna() # Pile pour la meilleure suite trouvée
for valeur in tab:
if pile_actuelle.est_vide() or valeur>pile_actuelle.sommet():
pile_actuelle.empiler(valeur)
else:
# Si pile_actuelle est plus longue que meilleure_pile, on la garde
if pile_actuelle.taille()>meilleure_pile.taille():
pile_temp=PileDyna()
while not pile_actuelle.est_vide():
pile_temp.empiler(pile_actuelle.depiler())
meilleure_pile=PileDyna()
while not pile_temp.est_vide():
meilleure_pile.empiler(pile_temp.depiler())
# Remise à 0 de pile_actuelle pour commencer une nouvelle suite
pile_actuelle=PileDyna()
pile_actuelle.empiler(valeur)
# Dernière vérification car pile_actuelle pourrait être plus grande que meilleure_pile
if pile_actuelle.taille()>meilleure_pile.taille():
pile_temp=PileDyna()
while not pile_actuelle.est_vide():
pile_temp.empiler(pile_actuelle.depiler())
meilleure_pile=PileDyna()
while not pile_temp.est_vide():
meilleure_pile.empiler(pile_temp.depiler())
pile_temp=PileDyna()
suite=[]
# On inverse la pile pour retrouver le bon ordre
while not meilleure_pile.est_vide():
pile_temp.empiler(meilleure_pile.depiler())
while not pile_temp.est_vide():
val=pile_temp.depiler()
suite.append(val)
meilleure_pile.empiler(val)
return suite,len(suite)
print(suite_croissante([5, 9, 7, 0, 2, 6, 9, 1, 2, 0]))
# Résultat : ([0, 2, 6, 9], 4)
La fonction doit chercher la plus grande suite croissante dans un tableau de valeurs. Pour cela j'ai utilisé des piles.